package main.剑指OfferⅡ;

import java.util.*;

public class Day21_Day24 {
    public static void main(String[] args) {
        System.out.println("**************************Day21**************************");
        System.out.println("剑指OfferⅡ062.实现前缀树");
        System.out.println("剑指OfferⅡ063.替换单词");
        System.out.println("剑指OfferⅡ064.神奇的字典");
        System.out.println("**************************Day22**************************");
        System.out.println("剑指OfferⅡ065.最短的单词编码");
        System.out.println("剑指OfferⅡ066.单词之和");
        System.out.println("剑指OfferⅡ067.最大的异或");
        System.out.println("**************************Day23**************************");
        System.out.println("剑指OfferⅡ068.查找插入位置");
        System.out.println("剑指OfferⅡ069.山峰数组的顶部");
        System.out.println("剑指OfferⅡ070.排序数组中只出现一次的数字");
        System.out.println("**************************Day24**************************");
        System.out.println("剑指OfferⅡ071.按权重生成随机数");
        System.out.println("剑指OfferⅡ072.求平方根");
        System.out.println("剑指OfferⅡ073.狒狒吃香蕉");
    }
}

class Offer62{
    class TireNode{//前缀树节点
        public int pass;//某个位置包含该字母的个数
        public int end;//某个位置以该字母结尾的个数
        public TireNode[] nexts;//下一个节点
        public TireNode(){
            pass=0;
            end=0;
            nexts=new TireNode[26];
        }
    }

    private TireNode root;

    public Offer62(){//首节点为空节点
        root=new TireNode();
    }

    public void insert(String word){//插入一个单词
        if (word==null) return;
        char[] chars=word.toCharArray();
        TireNode node=root;
        node.pass++;
        int index=0;
        for (int i=0;i< chars.length;i++){//依次遍历单词中的字符
            index=chars[i]-'a';
            if (node.nexts[index]==null) node.nexts[index]=new TireNode();//前缀树中该位置不存在该字符，创建该节点
            node=node.nexts[index];//前缀树中该位置存在该字符
            node.pass++;
        }
        node.end++;//以该节点结尾
    }

    public boolean search(String word){//查询单词插入过几次
        if (word==null) return false;
        char[] chars=word.toCharArray();
        TireNode node=root;
        int index=0;
        for (int i=0;i<chars.length;i++){
            index=chars[i]-'a';
            if (node.nexts[index]==null) return false;
            node=node.nexts[index];
        }
        if (node.end==0) return false;
        else return true;
    }

    public boolean startsWith(String pre){//包含该前缀的单词个数
        if (pre==null) return false;
        char[] chars=pre.toCharArray();
        TireNode node=root;
        int index=0;
        for (int i=0;i< chars.length;i++){
            index=chars[i]-'a';
            if (node.nexts[index]==null) return false;
            node=node.nexts[index];
        }
        return true;//包含了该单词最后字符的个数即是结果
    }
}

class Offer63{
    public boolean process(String s1,String s2){
        if (s1.length()>s2.length()) return false;
        char[] str1=s1.toCharArray(),str2=s2.toCharArray();
        int i=0;
        while (i<str1.length){
            if (str1[i]!=str2[i]) return false;
            i++;
        }
        return true;
    }
    public String replaceWords(List<String> dictionary, String sentence) {
        String[] sentences=sentence.split(" ");
        for (int i=0;i<sentences.length;i++){
            String temp="";
            for (int j=0;j<dictionary.size();j++){
                if (process(dictionary.get(j),sentences[i])&&(temp.equals("")||temp.length()>dictionary.get(j).length()))
                    temp=dictionary.get(j);
            }
            if (!temp.equals("")) sentences[i]=temp;
        }
        StringBuffer result=new StringBuffer();
        result.append(sentences[0]);
        for (int i=1;i<sentences.length;i++){
            result.append(" ");
            result.append(sentences[i]);
        }
        return result.toString();
    }
}

class Offer64{
    String[] words;
    public Offer64() {
        words=null;
    }

    public void buildDict(String[] dictionary) {
        words=dictionary;
    }

    public boolean search(String searchWord) {
        for (String word:words){
            if (word.length()==searchWord.length()){
                if (process(word,searchWord)) return true;
            }
        }
        return false;
    }

    public boolean process(String str1,String str2){
        char[] s1=str1.toCharArray(),s2=str2.toCharArray();
        int i=0,count=0;
        while (i<s1.length){
            if (s1[i]!=s2[i]) count++;
            if (count>1) return false;
            i++;
        }
        if (count==1) return true;
        else return false;
    }
}

class Offer65{
    public int minimumLengthEncoding(String[] words) {
        Set<String> good = new HashSet<String>(Arrays.asList(words));
        for (String word: words) {
            for (int k = 1; k < word.length(); ++k) {
                good.remove(word.substring(k));
            }
        }

        int ans = 0;
        for (String word: good) {
            ans += word.length() + 1;
        }
        return ans;
    }
}

class Offer66{
    Map<String,Integer> map;
    /** Initialize your data structure here. */
    public Offer66() {
        map=new HashMap<>();
    }

    public void insert(String key, int val) {
        map.put(key,val);
    }

    public int sum(String prefix) {
        int count=0;
        for (String words: map.keySet()){
            if (words.length()>=prefix.length()&&prefix.equals(words.substring(0,prefix.length()))) {
                count+=map.get(words);
            }
        }
        return count;
    }
}

class Offer67{
    int s[][];
    int idx;
    public int findMaximumXOR(int[] nums) {
        int n=nums.length;
        s=new int[31*n][2];
        int res=0;
        for(int num:nums) insert(num);
        for(int num:nums) res=Math.max(res,query(num));
        return res;
    }
    private void insert(int x) {
        int p=0;
        for(int i=30;i>=0;i--) {
            int u=x>>i&1;
            if(s[p][u]==0) s[p][u]=++idx;
            p=s[p][u];
        }
    }
    private int query(int x) {
        int p=0;
        int res=0;
        for(int i=30;i>=0;i--) {
            int u=x>>i&1;
            if(s[p][u^1]!=0) {
                res+=1<<i;
                p=s[p][u^1];
            }
            else p=s[p][u];
        }
        return res;
    }
}

class Offer68{
    public int searchInsert(int[] nums, int target) {
        int index=-1,left=0,right= nums.length;
        while (left<right){
            int mid=left+(right-left)/2;
            if (nums[mid]==target){
                index=mid;
                break;
            }else if (nums[mid]<target) left=mid+1;
            else right=mid;
        }
        if (index==-1) index=right;
        return index;
    }
}

class Offer69{
    public int peakIndexInMountainArray(int[] arr) {
        int left=0,right=arr.length-1,index=-1;
        while (left<right){
            int mid=left+(right-left)/2;
            if (arr[mid]>arr[mid-1]&&arr[mid]>arr[mid+1]){
                index=mid;
                break;
            }else if (arr[mid]<arr[mid+1]&&arr[mid]>arr[mid-1]) left=mid;
            else right=mid;
        }
        if (index==-1) index=left;
        return index;
    }
}

class Offer70{
    public int singleNonDuplicate(int[] nums) {
        int left=0,right= nums.length-1,result=-1;
        while (left<right){
            int mid=left+(right-left)/2;
            if (nums[mid]!=nums[mid-1]&&nums[mid]!=nums[mid+1]){
                result=mid;
                break;
            }else if (nums[mid]==nums[mid-1]){//
                if ((mid-left+1)%2==0) left=mid+1;
                else right=mid;
            }else {
                if ((mid-left)%2==0) left=mid;
                else right=mid-1;
            }
        }
        if (result==-1) result=left;
        return nums[result];
    }
}

class Offer71{
    double[] powerArr;
    Random random;
    public Offer71(int[] w) {
        random=new Random();
        int length=w.length,sum=0;
        double last=0;
        powerArr=new double[length];
        for (int n:w) sum+=n;//总和
        for (int i=0;i<length;i++){//以范围代替权重
            powerArr[i]=((w[i]*1.0)/(sum*1.0))*100+last;
            last=powerArr[i];
        }
    }

    public int pickIndex() {
        int index=-1;
        double rand= random.nextDouble()*100;
        for (int i=0;i< powerArr.length;i++){
            if (powerArr[i]-rand>1e-5){
                index=i;
                break;
            }
        }
        return index;
    }
}

class Offer72{
    public int mySqrt(int x) {
        return (int) Math.sqrt(x);
    }
}

class Offer73{
    public boolean process(int[] piles,int y,long h){
        long sum=0;
        for (int x:piles){
            int count=x/y;
            int temp=x%y==0 ? 0 : 1;
            sum+=count+temp;
        }
        return sum<=h;
    }
    public int minEatingSpeed(int[] piles, int h) {
        Arrays.sort(piles);
        int left=0,right=piles[piles.length-1]+1,result=right;
        while (left+1<right){
            int c=left+(right-left)/2;
            if (process(piles,c,h)){
                right=c;
                result=Math.min(result,c);
            }else {
                left=c;
            }
        }
        return result;
    }
}